package problem397;

import java.util.HashMap;

//379.整数替换
//https://leetcode.cn/problems/integer-replacement/description/

class Solution {
    HashMap<Long, Integer> map = new HashMap<>();
    public int integerReplacement(int n) {
        return dfs(n*1l);
    }
    public int dfs(long n) {
        if(n == 1) {
            return 0;
        }
        if(map.containsKey(n)) {
            return map.get(n);
        }
        if(n % 2 == 0) {
            int step = dfs(n/2)+1;
            map.put(n, step);
            return step;
        }else {
            int step = 1 + Math.min(dfs(n+1), dfs(n-1));
            map.put(n, step);
            return step;
        }
        
    }
}

/*
map[i]: 将i变为1所需的步数
*/